#include<stdio.h>
#include<time.h>

void shellsort(int *s,int len){
	int i,j,gap;
	int temp;
	for(gap=len/2;gap>0;gap/=2){
		for(i=gap;i<len;i+=1){
			for(j=i-gap;j>=0 && s[j]>s[j+gap];j-=gap){
				temp=s[j+gap];
				s[j+gap]=s[j];
				s[j]=temp;
			}
		}
	}
}

void swap(int *a,int *b){
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
} 

void quicksort(int *s,int left,int right){
	int i,j;
	if(left<right){
		i=left;
		j=right+1;
		while(1){
			do{
				i++;
			}while(i<right&&s[i]<=s[left]);
			do{
				j--;
			}while(j>left&&s[j]>=s[left]);
			if(i<j){
				swap(&s[i],&s[j]);
			}
			else{
				break;
			}
		}
		swap(&s[j],&s[left]);
		quicksort(s,j+1,right);
		quicksort(s,left,j-1);
	}
}

int main(){
	int sum=0;
	for(int i=0;i<100;i++){
		sum+=i;
	}
	int test1[1000]={476,622,311,377,285,527,928,799,680,50,456,991,177,574,608,552,418,932,962,292,554,700,87,975,272,658,515,32,505,833,678,683,433,62,108,598,158,425,991,99,315,160,444,350,44,348,931,951,981,55,499,58,560,590,462,637,255,804,976,897,374,344,486,773,725,280,901,151,541,357,112,748,360,296,30,395,790,214,186,773,5,296,37,319,680,182,522,315,507,734,720,340,238,847,621,345,321,954,537,452,607,451,25,266,286,701,309,957,574,492,836,281,583,719,183,53,408,877,651,979,549,990,450,905,193,318,812,800,516,998,82,36,175,452,68,373,590,76,131,526,124,46,945,477,910,10,688,586,648,922,601,403,621,439,854,255,670,278,690,506,328,179,511,792,234,575,639,525,255,591,487,941,882,821,409,863,127,91,58,671,946,341,188,260,754,710,68,175,813,558,182,334,98,498,87,32,651,652,972,218,362,37,657,393,925,536,189,448,477,41,12,108,251,6,60,798,236,597,444,266,871,302,818,430,660,882,452,348,696,60,666,147,478,903,834,963,440,760,379,440,150,101,182,585,158,798,233,929,916,515,782,317,268,967,189,368,102,419,533,524,49,486,848,513,892,371,424,851,321,68,372,855,434,206,952,445,664,908,20,141,898,880,867,939,835,784,254,765,839,662,170,695,263,626,784,252,523,555,52,840,568,348,160,140,803,756,922,850,180,608,331,353,773,269,161,627,509,297,39,205,776,785,419,814,834,793,569,572,708,959,326,140,590,336,568,784,358,7,372,846,216,715,447,758,462,417,881,996,401,130,167,776,841,431,89,258,593,73,363,113,647,85,535,773,435,9,482,707,621,216,566,370,228,820,945,748,372,989,156,247,32,452,94,301,985,933,130,752,85,333,926,554,491,295,181,652,94,958,696,637,976,30,216,942,313,131,231,523,472,111,864,772,562,438,108,877,952,789,15,379,957,50,82,313,953,413,986,809,896,783,993,734,759,26,19,201,207,97,83,715,450,73,335,243,790,649,329,264,744,654,896,106,34,482,791,308,768,725,884,628,344,165,828,966,633,474,581,677,517,245,340,227,553,90,344,988,156,651,710,566,382,880,142,252,12,660,541,659,929,377,29,380,119,558,187,732,750,344,799,248,564,183,441,469,54,539,650,222,277,559,337,551,917,284,103,26,994,696,189,760,220,977,252,691,4,37,653,705,55,228,946,683,771,528,892,47,480,27,695,747,409,562,291,259,418,305,277,220,492,551,189,506,448,595,369,303,424,911,178,293,748,948,812,334,203,743,564,610,384,786,670,249,447,166,325,465,752,847,214,514,428,888,526,760,909,697,179,81,283,342,9,408,820,722,639,441,99,68,625,773,877,513,447,1,928,418,485,218,269,743,612,708,591,523,857,123,460,906,396,9,284,497,996,929,520,230,346,595,340,55,379,890,560,63,346,698,563,142,421,998,113,984,382,721,184,281,828,699,981,79,715,422,844,393,818,242,655,78,604,278,446,569,658,47,288,756,207,854,937,243,843,93,989,490,187,826,812,297,993,864,607,463,816,314,482,589,988,233,754,500,535,88,344,17,430,374,478,536,14,867,810,704,65,223,785,413,837,415,958,251,199,193,499,2,291,723,431,957,384,527,136,495,706,978,371,120,727,428,570,812,503,258,45,517,765,147,252,762,427,232,44,904,429,768,608,336,485,882,490,377,951,716,682,152,669,251,734,141,414,44,259,455,858,899,451,754,385,594,863,777,965,445,598,23,197,403,375,962,420,607,172,346,929,663,760,326,656,101,50,424,185,557,266,426,479,318,707,32,268,28,649,856,675,37,325,760,382,187,568,911,873,298,860,135,463,738,761,729,651,838,342,857,105,270,334,451,214,91,670,47,590,185,363,329,997,881,569,740,696,408,674,71,300,546,347,560,991,739,102,537,550,896,275,337,535,225,232,652,128,985,299,269,55,769,85,219,819,434,545,201,683,393,973,27,374,992,297,286,322,275,990,623,233,57,921,143,201,500,287,309,267,585,499,716,271,219,150,710,549,805,182,394,487,904,538,290,213,932,317,216,793,154,890,250,333,225,759,563,129,607,780,932,361,363,277,19,374,249,150,915,972,229,743,644,548,507,929,68,923,782,120,102,875,456,289,379,856,194,605,198,477,332,319,427,352,143,586,283,404,537,470,641,622,521,669,825,442,203,33,498,54,774,361,9,103,460,468,896,99,570,757,191,703,962,767,626,402,405,250,994,161,500,750,625,20,152,40,888,41,32};
	int test2[1000]={476,622,311,377,285,527,928,799,680,50,456,991,177,574,608,552,418,932,962,292,554,700,87,975,272,658,515,32,505,833,678,683,433,62,108,598,158,425,991,99,315,160,444,350,44,348,931,951,981,55,499,58,560,590,462,637,255,804,976,897,374,344,486,773,725,280,901,151,541,357,112,748,360,296,30,395,790,214,186,773,5,296,37,319,680,182,522,315,507,734,720,340,238,847,621,345,321,954,537,452,607,451,25,266,286,701,309,957,574,492,836,281,583,719,183,53,408,877,651,979,549,990,450,905,193,318,812,800,516,998,82,36,175,452,68,373,590,76,131,526,124,46,945,477,910,10,688,586,648,922,601,403,621,439,854,255,670,278,690,506,328,179,511,792,234,575,639,525,255,591,487,941,882,821,409,863,127,91,58,671,946,341,188,260,754,710,68,175,813,558,182,334,98,498,87,32,651,652,972,218,362,37,657,393,925,536,189,448,477,41,12,108,251,6,60,798,236,597,444,266,871,302,818,430,660,882,452,348,696,60,666,147,478,903,834,963,440,760,379,440,150,101,182,585,158,798,233,929,916,515,782,317,268,967,189,368,102,419,533,524,49,486,848,513,892,371,424,851,321,68,372,855,434,206,952,445,664,908,20,141,898,880,867,939,835,784,254,765,839,662,170,695,263,626,784,252,523,555,52,840,568,348,160,140,803,756,922,850,180,608,331,353,773,269,161,627,509,297,39,205,776,785,419,814,834,793,569,572,708,959,326,140,590,336,568,784,358,7,372,846,216,715,447,758,462,417,881,996,401,130,167,776,841,431,89,258,593,73,363,113,647,85,535,773,435,9,482,707,621,216,566,370,228,820,945,748,372,989,156,247,32,452,94,301,985,933,130,752,85,333,926,554,491,295,181,652,94,958,696,637,976,30,216,942,313,131,231,523,472,111,864,772,562,438,108,877,952,789,15,379,957,50,82,313,953,413,986,809,896,783,993,734,759,26,19,201,207,97,83,715,450,73,335,243,790,649,329,264,744,654,896,106,34,482,791,308,768,725,884,628,344,165,828,966,633,474,581,677,517,245,340,227,553,90,344,988,156,651,710,566,382,880,142,252,12,660,541,659,929,377,29,380,119,558,187,732,750,344,799,248,564,183,441,469,54,539,650,222,277,559,337,551,917,284,103,26,994,696,189,760,220,977,252,691,4,37,653,705,55,228,946,683,771,528,892,47,480,27,695,747,409,562,291,259,418,305,277,220,492,551,189,506,448,595,369,303,424,911,178,293,748,948,812,334,203,743,564,610,384,786,670,249,447,166,325,465,752,847,214,514,428,888,526,760,909,697,179,81,283,342,9,408,820,722,639,441,99,68,625,773,877,513,447,1,928,418,485,218,269,743,612,708,591,523,857,123,460,906,396,9,284,497,996,929,520,230,346,595,340,55,379,890,560,63,346,698,563,142,421,998,113,984,382,721,184,281,828,699,981,79,715,422,844,393,818,242,655,78,604,278,446,569,658,47,288,756,207,854,937,243,843,93,989,490,187,826,812,297,993,864,607,463,816,314,482,589,988,233,754,500,535,88,344,17,430,374,478,536,14,867,810,704,65,223,785,413,837,415,958,251,199,193,499,2,291,723,431,957,384,527,136,495,706,978,371,120,727,428,570,812,503,258,45,517,765,147,252,762,427,232,44,904,429,768,608,336,485,882,490,377,951,716,682,152,669,251,734,141,414,44,259,455,858,899,451,754,385,594,863,777,965,445,598,23,197,403,375,962,420,607,172,346,929,663,760,326,656,101,50,424,185,557,266,426,479,318,707,32,268,28,649,856,675,37,325,760,382,187,568,911,873,298,860,135,463,738,761,729,651,838,342,857,105,270,334,451,214,91,670,47,590,185,363,329,997,881,569,740,696,408,674,71,300,546,347,560,991,739,102,537,550,896,275,337,535,225,232,652,128,985,299,269,55,769,85,219,819,434,545,201,683,393,973,27,374,992,297,286,322,275,990,623,233,57,921,143,201,500,287,309,267,585,499,716,271,219,150,710,549,805,182,394,487,904,538,290,213,932,317,216,793,154,890,250,333,225,759,563,129,607,780,932,361,363,277,19,374,249,150,915,972,229,743,644,548,507,929,68,923,782,120,102,875,456,289,379,856,194,605,198,477,332,319,427,352,143,586,283,404,537,470,641,622,521,669,825,442,203,33,498,54,774,361,9,103,460,468,896,99,570,757,191,703,962,767,626,402,405,250,994,161,500,750,625,20,152,40,888,41,32};
	clock_t start1,start2,end1,end2;
	start1=clock();
	shellsort(test1,1000);
	for(int i=0;i<1000;i++){
		printf("%d,",test1[i]);
	}
	printf("\n");
	end1=clock();
	double time1=(double)(end1-start1)/CLOCKS_PER_SEC;
	printf("shellsort:%f seconds\n",time1);
	start2=clock();
	quicksort(test2,0,999);
	for(int i=0;i<1000;i++){
		printf("%d,",test2[i]);
	}
	printf("\n");
	end2=clock();
	double time2=(double)(end2-start2)/CLOCKS_PER_SEC;
	printf("quicksort:%f seconds\n",time2);
	if(time1>time2){
		printf("1000 numbers, quicksort better");
	}
	else{
		printf("1000 numbers, shellsort better");
	}
	return 0;
}